#include "test_bst.h"




void refresh_seq_buffer()
{
    bst_tree_seq[0] = '\0';
    seq_ptr = 0;
}



void bst_preorder_seq(bst_tree r)
{
    if (NULL == r)
        return;

    seq_ptr += snprintf( bst_tree_seq + seq_ptr, BST_SEQ_BUFFER_MAX_LEN - seq_ptr,"%d ", r->data);
    bst_preorder_seq(r->left);
    bst_preorder_seq(r->right);

}
void bst_inorder_seq(bst_tree r)
{
    if (NULL == r)
        return;
    bst_inorder_seq(r->left);
    
    seq_ptr += snprintf( bst_tree_seq + seq_ptr, BST_SEQ_BUFFER_MAX_LEN - seq_ptr,"%d ", r->data);
    

    bst_inorder_seq(r->right);
}
void bst_postorder_seq(bst_tree r)
{
    if (NULL == r)
        return;
    bst_postorder_seq(r->left);
    bst_postorder_seq(r->right);
    seq_ptr += snprintf( bst_tree_seq + seq_ptr, BST_SEQ_BUFFER_MAX_LEN  - seq_ptr,"%d ", r->data);
}



static void test_bst_insert_lll(void)
{
    bst_tree rt = NULL;
    bst_tree_insert(&rt, 3);
    bst_tree_insert(&rt, 2);
    bst_tree_insert(&rt, 1);

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

   

    CU_ASSERT_STRING_EQUAL(bst_tree_seq, "3 2 1 \n1 2 3 \n");

    bst_tree_free(&rt);
}



static void test_bst_insert_rrr(void)
{
    bst_tree rt = NULL;
    bst_tree_insert(&rt, 1);
    bst_tree_insert(&rt, 2);
    bst_tree_insert(&rt, 3);

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL(bst_tree_seq, "1 2 3 \n1 2 3 \n");


    bst_tree_free(&rt);
}
static int cmp(const void *a, const void *b)
{
    return *(int *) a - * (int *) b;
}
static void test_bst_insert_rand( void )
{
    bst_tree rt = NULL;


    char seq_str[200];
    memset(seq_str, 0, sizeof(seq_str));
    srand(time(NULL));
    int seq[10];
    for (int i = 0; i < 10; ++i) {
        int v = rand();
        seq[i] = v;    
        bst_tree_insert( &rt, v );
    }
    int p = 0;
    qsort(seq, 10, sizeof(seq[0]),cmp);
    for (int i = 0;i < 10; ++i) 
        p += sprintf(seq_str + p, "%d ", seq[i]);
    seq_str[p++]='\n';
    seq_str[p++]='\0'; 

    refresh_seq_buffer();
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++]='\n';
    bst_tree_seq[seq_ptr++]='\0';

    printf("expected: %s", seq_str);
    printf("------------\n");
    printf("actually: %s", bst_tree_seq);
    CU_ASSERT_STRING_EQUAL(bst_tree_seq, seq_str);
    
    bst_tree_free( &rt );
}
static void test_bst_find(void)
{
    bst_tree rt = NULL;
    bst_tree_insert(&rt, 7);
    bst_tree_insert(&rt, 4);
    bst_tree_insert(&rt, 6);
    CU_ASSERT_TRUE( bst_tree_find(&rt, 7));
    CU_ASSERT_TRUE( bst_tree_find(&rt, 4));
    CU_ASSERT_TRUE( bst_tree_find(&rt, 6));

    CU_ASSERT_FALSE( bst_tree_find(&rt, 10));
    CU_ASSERT_FALSE( bst_tree_find(&rt, 20));
    CU_ASSERT_FALSE( bst_tree_find(&rt, 30));

    bst_tree_free(&rt);
}
static void test_bst_delete_root(void)
{
    bst_tree rt = NULL;
    bst_tree_insert( &rt, 7 );
    bst_tree_insert( &rt, 4 );
    bst_tree_insert( &rt, 6 );


    CU_ASSERT_FALSE( bst_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  bst_tree_delete( &rt, 7 ) );

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( bst_tree_seq, "6 4 \n4 6 \n");


    bst_tree_free( &rt );
}
static void test_bst_delete_leaf(void)
{
    bst_tree rt = NULL;
    bst_tree_insert( &rt, 7 );
    bst_tree_insert( &rt, 6 );
    bst_tree_insert( &rt, 8 );
    bst_tree_insert( &rt, 9 );

    CU_ASSERT_FALSE( bst_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  bst_tree_delete( &rt, 9 ) );

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( bst_tree_seq, "7 6 8 \n6 7 8 \n");


    bst_tree_free( &rt );
}

static void test_bst_delete_simple(void)
{
    bst_tree rt = NULL;
    bst_tree_insert( &rt, 8 );
    bst_tree_insert( &rt, 9 );
    bst_tree_insert( &rt, 10 );
    bst_tree_insert( &rt, 6 );
    bst_tree_insert( &rt, 5 );
    bst_tree_insert( &rt, 7 );


    CU_ASSERT_FALSE( bst_tree_delete( &rt, 22) );
    CU_ASSERT_TRUE(  bst_tree_delete( &rt, 6 ) );

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( bst_tree_seq, "8 5 7 9 10 \n5 7 8 9 10 \n");


    bst_tree_free( &rt );
}

static void test_bst_delete_only_one(void)
{
    bst_tree rt = NULL;
    bst_tree_insert( &rt, 7 );

    CU_ASSERT_FALSE( bst_tree_delete( &rt, 10) );
    CU_ASSERT_TRUE(  bst_tree_delete( &rt, 7 ) );

    refresh_seq_buffer();

    bst_preorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++] = '\n';
    bst_tree_seq[seq_ptr++] = '\0';

    CU_ASSERT_STRING_EQUAL( bst_tree_seq, "\n\n");


    bst_tree_free( &rt );
}

static void test_bst_delete_rand( void )
{
    bst_tree rt = NULL;


    char seq_str[200];
    memset(seq_str, 0, sizeof(seq_str));
    srand(time(NULL));
    int seq[10];

    int dval;
    for (int i = 0; i < 10; ++i) {
        
        

        int v = rand();
        if (i == 9)
            dval = v;
        seq[i] = v;    
        bst_tree_insert( &rt, v );
    }
    int p = 0;
    qsort(seq, 9, sizeof(seq[0]),cmp);
    for (int i = 0;i < 9; ++i) 
        p += sprintf(seq_str + p, "%d ", seq[i]);
    seq_str[p++]='\n';
    seq_str[p++]='\0'; 


    bst_tree_delete( &rt, dval);
    refresh_seq_buffer();
    bst_inorder_seq(rt);
    bst_tree_seq[seq_ptr++]='\n';
    bst_tree_seq[seq_ptr++]='\0';

    printf("expected: %s", seq_str);
    printf("------------\n");
    printf("actually: %s", bst_tree_seq);
    CU_ASSERT_STRING_EQUAL(bst_tree_seq, seq_str);
    
    bst_tree_free( &rt );
}


static CU_TestInfo test_bstInsert[] = {
    {"test_bst_lll_insert", test_bst_insert_lll},
    {"test_bst_rrr_insert", test_bst_insert_rrr},
    {"test_bst_rand_insert", test_bst_insert_rand},
    
    CU_TEST_INFO_NULL,
};
static CU_TestInfo test_bstFind[] = {
    {"test_bst_find", test_bst_find},
    CU_TEST_INFO_NULL,
};
static CU_TestInfo test_bstDelete[] = {
    {"test_bst_delete_root", test_bst_delete_root},
    {"test_bst_delete_leaf", test_bst_delete_leaf},
    {"test_bst_delete_simple", test_bst_delete_simple},
    {"test_bst_delete_only_one", test_bst_delete_only_one},
    {"test_bst_delete_rand", test_bst_delete_rand},
    CU_TEST_INFO_NULL,
};

static CU_SuiteInfo suites[] = {
    {"suite_test_insert", NULL, NULL, NULL, NULL, test_bstInsert},
    {"suite_test_find",   NULL, NULL, NULL, NULL, test_bstFind},
    {"suite_test_delete", NULL, NULL, NULL, NULL, test_bstDelete},
    CU_SUITE_INFO_NULL,
};

void AddTests(void)
{
    assert(NULL != CU_get_registry());
    assert(!CU_is_test_running());

    if (CU_register_suites(suites) != CUE_SUCCESS) {
        fprintf(stderr, "suite registration failed - %s \n", 
            CU_get_error_msg());        
        exit(EXIT_FAILURE);
    }
}